package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder3
import java.util.*
import kotlin.collections.ArrayList

/**
 * https://leetcode.cn/problems/cousins-in-binary-tree-ii/description
 * ```
 * 2641. 二叉树的堂兄弟节点 II
 * 给你一棵二叉树的根 root ，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 。
 * 如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟 。
 * 请你返回修改值之后，树的根 root 。
 * 注意，一个节点的深度指的是从树根节点到这个节点经过的边数。
 *
 *
 * 示例 1：
 * 输入：root = [5,4,9,1,10,null,7]
 * 输出：[0,0,0,7,7,null,11]
 * 解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
 * - 值为 5 的节点没有堂兄弟，所以值修改为 0 。
 * - 值为 4 的节点没有堂兄弟，所以值修改为 0 。
 * - 值为 9 的节点没有堂兄弟，所以值修改为 0 。
 * - 值为 1 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
 * - 值为 10 的节点有一个堂兄弟，值为 7 ，所以值修改为 7 。
 * - 值为 7 的节点有两个堂兄弟，值分别为 1 和 10 ，所以值修改为 11 。
 *
 * 示例 2：
 * 输入：root = [3,1,2]
 * 输出：[0,0,0]
 * 解释：上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
 * - 值为 3 的节点没有堂兄弟，所以值修改为 0 。
 * - 值为 1 的节点没有堂兄弟，所以值修改为 0 。
 * - 值为 2 的节点没有堂兄弟，所以值修改为 0 。
 *
 *
 * 提示：
 * 树中节点数目的范围是 [1, 105] 。
 * 1 <= Node.val <= 104
 * ```
 */
class leetcode_2641 {
    @Test
    fun test_1() {
        val root = TreeNode(3)
        root.left = TreeNode(1)
        root.right = TreeNode(1)
        val actual = replaceValueInTree(root)
        val expected = arrayListOf(0, 0, 0)
        Assert.assertEquals(expected, printLevelOrder3(actual))
    }


    private fun replaceValueInTree(root: TreeNode?): TreeNode? {
        /**
        题型：二叉树的层级遍历

        思路：
        1 对于根节点，始终为0
        2 对于其他节点，
        遍历时，收集当前层的节点，以及它们下一层的层和，那么下一层的值，等于下一层的层和 减去 下一层的兄弟和。
         */
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return null
        }
        // 3 确定单层递归的处理逻辑: 非递归，层级遍历
        val queque: LinkedList<TreeNode> = LinkedList()
        queque.offer(root)

        // 根节点始终 为 0
        root.`val` = 0
        while (!queque.isEmpty()) {
            var size: Int = queque.size
            // 收集当前层的节点
            val currentLevelNodes: ArrayList<TreeNode> = ArrayList()

            // 收集下一层的节点和
            var nextLevelSum: Int = 0

            while (size-- > 0) {
                val node = queque.poll()
                currentLevelNodes.add(node)

                node.left?.let {
                    queque.offer(it)
                    nextLevelSum = nextLevelSum + it.`val`
                }
                node.right?.let {
                    queque.offer(it)
                    nextLevelSum = nextLevelSum + it.`val`
                }
            }

            // 更新下一层的数值: 下一层节点的值等于下一层的层和 - 下一层节点的兄弟和
            for (item in currentLevelNodes) {
                // 下一层节点的兄弟和
                var brotherSum: Int = 0

                item.left?.let {
                    brotherSum = brotherSum + it.`val`
                }

                item.right?.let {
                    brotherSum = brotherSum + it.`val`
                }

                // 下一层节点的值等于下一层的层和 - 下一层节点的兄弟和
                item.left?.let {
                    it.`val` = nextLevelSum - brotherSum
                }
                item.right?.let {
                    it.`val` = nextLevelSum - brotherSum
                }
            }
        }
        return root
    }
}
